package org.liaohailong.helloworld.hash;

/**
 * Author: liaohailong
 * Date: 2021/5/21
 * Time: 21:31
 * Description:
 **/
public class MyHashMap {
    int size = 1 << 10;
    final Node[] bucket;

    /**
     * Initialize your data structure here.
     */
    public MyHashMap() {
        bucket = new Node[size];
    }

    /**
     * value will always be non-negative.
     */
    public void put(int key, int value) {
        int index = index(key);
        Node find = contains(key);
        if (find != null) {
            find.val = value;
        } else {
            Node node = bucket[index];
            if (node == null) {
                node = new Node(key, value);
                bucket[index] = node;
            } else {
                last(node).next = new Node(key, value);
            }
        }
    }

    /**
     * Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
     */
    public int get(int key) {
        int index = index(key);
        Node node = bucket[index];
        Node find = find(node, key);
        if (find == null) return -1;
        return find.val;
    }


    private int index(int key) {
        return key % size;
    }

    private Node last(Node head) {
        Node node = head;
        while (node.next != null) node = node.next;
        return node;
    }

    public void remove(int key) {
        int index = index(key);
        Node node = bucket[index];
        if (node == null) return;
        node = remove(node, key);
        bucket[index] = node;
    }

    private final Node empty = new Node(-1, -1);

    private Node remove(Node head, int key) {
        empty.next = head;
        Node node = empty;
        while (node != null && node.next != null) {
            if (node.next.key == key) node.next = node.next.next;
            node = node.next;
        }
        Node next = empty.next;
        empty.next = null;
        return next;
    }

    /**
     * Returns true if this set contains the specified element
     */
    public Node contains(int key) {
        int index = index(key);
        Node node = bucket[index];
        if (node == null) return null;
        return find(node, key);
    }

    private Node find(Node head, int key) {
        empty.next = head;
        Node node = empty;
        while (node.next != null) {
            if (node.next.key == key) return node.next;
            node = node.next;
        }
        empty.next = null;
        return null;
    }

    private static final class Node {
        int key;
        int val;
        Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
}
